// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-06 00:06
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;


import com.DataStruct.Tree.TwoBinaryTree.TreeNode;
import com.DataStruct.Tree.TwoBinaryTree.Utils;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class LowestCommonAncestor {
    /**
     * 二叉树的最近公共祖先
     * 自顶向下-> 存储访问路径
     * 可以使用栈记录访问节点的路径 -> 两个节点一定存在公共祖先
     */

    List<TreeNode> t = new ArrayList<>();
    List<TreeNode> f = new ArrayList<>();

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return null;
        }
        find(root, p, t);
        find(root, q, f);
        // 获取两个列表中最开始相同的节点
        return getCommon(t, f);
        // 两个列表都是从根节点开始，如果两个列表的访问路径中，除了根节点外不存在相同的节点，则两个节点的公共祖先就是根节点
    }

    /**
     * 用于获取两个列表的公共父节点
     *
     * @param t 列表1
     * @param f 列表2
     */
    private TreeNode getCommon(List<TreeNode> t, List<TreeNode> f) {
        // 首先移除根节点 root
        TreeNode root = t.remove(0);
        f.remove(0);
        // 默认是th列表中的节点大于fh列表中的节点
        if (t.isEmpty() || f.isEmpty()) {
            return root;
        }
        TreeNode th = t.get(0);
        TreeNode fh = f.get(0);

        while (th.val != fh.val) {
            if (th.val < fh.val) {
                th = t.remove(0);
            } else {
                fh = f.remove(0);
            }
            if (t.isEmpty() || f.isEmpty()) {
                return root;
            }
        }
        while ((!t.isEmpty() && !f.isEmpty()) && (t.get(0).val == f.get(0).val)) {
            th = t.remove(0);
            fh = f.remove(0);
        }
        return th;
    }

    /**
     * 在给定树中存储访问指定节点的路径
     *
     * @param root 根节点
     * @param p    查找节点
     * @param list 记录路径的链表
     */
    private void find(TreeNode root, TreeNode p, List<TreeNode> list) {
        if (root == null) {
            return;
        }
        list.add(root);
        if (root.val > p.val) {
            find(root.left, p, list);
        } else if (root.val < p.val) {
            find(root.right, p, list);
        }
    }


    @Test
    public void shout() {
        int[] nodes = {6, 2, 8, 0, 4, 7, 9, -1, -1, 3, 5};
        Utils utils = new Utils();
        TreeNode<Integer> root = utils.constructTreeBySequence(nodes);
        System.out.println(new LowestCommonAncestor().lowestCommonAncestor(root, root.left, root.right));

    }
}
